/**
 * @Question.Title: 单词拆分
 * @Question.No: 139
 * @Author: DQ
 * @Date: 2021-04-22 10:55:57
 * @Description: 
 */
//给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 
//
// 说明： 
//
// 
// 拆分时可以重复使用字典中的单词。 
// 你可以假设字典中没有重复的单词。 
// 
//
// 示例 1： 
//
// 输入: s = "leetcode", wordDict = ["leet", "code"]
//输出: true
//解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
// 
//
// 示例 2： 
//
// 输入: s = "applepenapple", wordDict = ["apple", "pen"]
//输出: true
//解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
//     注意你可以重复使用字典中的单词。
// 
//
// 示例 3： 
//
// 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
//输出: false
// 
// Related Topics 动态规划 
// 👍 949 👎 0

package dq.leetcode.editor.cn;

import java.util.*;

public class WordBreak {
    public static void main(String[] args) {
        Solution solution = new WordBreak().new Solution();
        String s = "catsandog";
        List<String> wordDict = Arrays.asList("cats", "dog", "sand", "and", "cat");
        System.out.println(solution.wordBreak(s, wordDict));

    }

    //leetcode submit region begin(Prohibit modification and deletion)

class Solution {

    public boolean wordBreak(String s, List<String> wordDict) {
//        return wordBreakWithDfs(s, wordDict);
        return  wordBreakWithDP(s, wordDict);
    }

    public boolean wordBreakWithDP(String s, List<String> wordDict){
        boolean[] dp = new boolean[s.length()+1];
        dp[s.length()] = true;
        Set<String> dict = new HashSet<>(wordDict);

        for(int i = s.length()-1; i >= 0; i--){
            for(int j = i+1; j < dp.length && !dp[i]; j++){
                dp[i] = dp[j] & dict.contains(s.substring(i, j));
            }
        }
        return dp[0];
    }
    public boolean wordBreakWithDfs(String s, List<String> wordDict) {
        //词典
        Set<String> dict = new HashSet<>(wordDict);
        int[] dp = new int[s.length()];
        return dfs(s, 0, dict, dp);
    }
    private boolean dfs(String s, int i, Set<String> dict, int[] dp){
        //如果到达最后
        if(i>=s.length()) {
            return true;
        }
        if(dp[i]!=0) {
            return dp[i]==1;
        }
        for(int k = i+1; k <= s.length(); k++){
            if(dict.contains(s.substring(i, k)) && dfs(s, k, dict, dp)){
                dp[i] = 1;
                return true;
            }
        }
        dp[i] = -1;
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}